package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * 552. 学生出勤记录 II
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/18 9:17
 */
public class CheckRecord {

    public static void main(String[] args) {
        CheckRecord test = new CheckRecord();

        // 8
//        int n = 2;

        // 94
//        int n = 5;

        // 3536
//        int n = 10;

        // 183236316
//        int n = 10101;

        // 749184020
        int n = 100000;

        int aa = test.checkRecord(n);

        System.out.println(aa);
    }

    public int checkRecord(int n) {
        if (n == 1) {
            return 3;
        }
        long[] arr1 = new long[6];
        long[] arr2 = new long[6];
        arr1[0] = 1;
        arr1[1] = 1;
        arr1[2] = 1;
        for (int i = 1; i < n; i++) {
            long value = arr1[0];
            arr2[0] += value;
            arr2[1] += value;
            arr2[2] += value;

            value = arr1[1];
            arr2[1] += value;
            arr2[3] += value;

            value = arr1[2];
            arr2[0] += value;
            arr2[1] += value;
            arr2[4] += value;

            value = arr1[3];
            arr2[1] += value;
            arr2[5] += value;

            value = arr1[4];
            arr2[0] += value;
            arr2[1] += value;

            value = arr1[5];
            arr2[1] += value;
            for (int j = 0; j < 6; j++) {
                arr1[j] = arr2[j] % 1000000007;
                arr2[j] = 0;
            }
        }
        long v = 0L;
        for (int j = 0; j < 6; j++) {
            v += arr1[j];
        }
        return (int) (v % 1000000007);
    }

}
